/**
 * 反转链表
 *
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
 * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 *
 * 示例 1：
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 *
 * 示例 2：
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 *
 * 提示：
 * 链表中节点数目为 n
 * 1 <= n <= 500
 * -500 <= Node.val <= 500
 * 1 <= left <= right <= n
 *
 * 进阶： 你可以使用一趟扫描完成反转吗？
 */

/**
 * 这题我们只需要将 leftVal 和 rightVal 的位置找出来就可以了
 * 然后直接进行头插后面需要反转的节点
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {
    public ListNode reverseBetween(ListNode head, int leftVal, int rightVal) {

        // 虚拟头结点
        ListNode newHead = new ListNode();
        newHead.next = head;

        // 分别记录 left right 和两边的节点
        ListNode cur = newHead.next;
        ListNode prevLeft = cur;
        ListNode nextRight = cur;
        ListNode left = cur;
        ListNode right = cur;

        ListNode prev = newHead;

        int k = 0;
        while (cur != null) {

            k++;
            if (k == leftVal) {
                left = cur;
                prevLeft = prev;
            }

            if (k == rightVal) {
                right = cur;
                nextRight = cur.next;
                break;
            }

            prev = cur;
            cur = prev.next;
        }

        prev = prevLeft;
        cur = prev.next;

        // 头插
        // prevLeft -> tmp -> .... -> prev -> cur -> next -> ... -> nextRight
        // prevLeft -> cur -> tmp -> .... -> prev -> next -> ... -> nextRight

        while (cur != nextRight) {

            ListNode next = cur.next;
            ListNode tmp = prevLeft.next;

            // 这里要注意重合的情况, 也就是一开始头插的节点
            if (cur == tmp) {
                prev = cur;
                cur = prev.next;
                continue;
            }

            prevLeft.next = cur;
            cur.next = tmp;
            prev.next = next;

            cur = prev.next;
        }

        return newHead.next;
    }

    // 测试用例
    public static void main(String[] args) {

        Main test = new Main();

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        test.reverseBetween(node1, 2, 4);
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}